package month1;
import java.util.*;
public class SolveNQueens51_06 {
    public static void main(String[] args) {
        System.out.println(solveNQueens(8));
    }

    static int N;
    static int[] queens;
    static List<List<String>> solveNQueens(int n) {
        N = n;
        queens = new int[n];
        List<List<String>> ret = new ArrayList<>();
        traceback(ret, 0, "");
        return ret;
    }
    static void traceback(List<List<String>> ret, int index, String tmp) {
        if (index == N) {
            List<String> strs = new ArrayList<>();
            for(char c: tmp.toCharArray()) {
                int n = N;
                String str = "";
                while(n-- > 0) {
                    if (n == c - '0') {
                        str += "Q";
                    } else {
                        str += ".";
                    }
                }
                strs.add(str);
            }
            ret.add(strs);
            return;
        }
        for(int j = 0;j < N; ++j) {
            queens[index] = j;
            if (isVliad(index)) {
                traceback(ret, index + 1, tmp + j);
            }
        }
    }
    static boolean isVliad(int j) {
        for(int i = 0;i < j; ++i) {
            if (queens[i] == queens[j] || Math.abs(i - j) == Math.abs(queens[i] - queens[j])) {
                return false;
            }
        }
        return true;
    }
}
